package leetcode;

/**
 * 338. 比特位计数
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 示例 2：
 * <p>
 * 输入：n = 5
 * 输出：[0,1,1,2,1,2]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 * 3 --> 11
 * 4 --> 100
 * 5 --> 101
 */
public class CountBits {

    /**
     * 位运算,每一位进行如下运算。
     *
     * TIPS：不是直接用int类型计算,而是先把十进制转换成二进制再运算,运算结果再转回十进制
     *
     * <p>
     * '&' 与 都为1才是1。含义与'&&'一致
     * '|' 或 只要有1就是1。含义与'||'一致
     * '~' 非 取反，0则取1，1则取0。含义与'!' 一致
     * '^' 异或 不一样才取1，一样则取0。含义与'!='一致
     *
     * @param n
     * @return
     */
    public int[] countBits(int n) {

        int[] count = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            count[i] = countOnes(i);
        }

        return count;
    }


    /**
     * 动态规划 没看懂
     *
     * @param n
     * @return
     */
//    public int[] countBits1(int n) {
//        int[] bits = new int[n + 1];
//        for (int i = 1; i <= n; i++) {
//            bits[i] = bits[i & (i - 1)] + 1;
//        }
//        return bits;
//    }
    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            // 最后一位 由 1 变成 0
            x = x & (x - 1);
            ones++;
        }

        return ones;
    }

}
